// 计算右侧小于当前元素的个数
// Created by madison on 2022/12/1.
//

#include "vector"

using namespace std;

class Solution {
    vector<int> c;
    vector<int> a;

    void Init(int length) {
        c.resize(length, 0);
    }

    int LowBit(int x) {
        return x & (-x);
    }

    void Update(int pos) {
        while (pos < c.size()) {
            c[pos] += 1;
            pos += LowBit(pos);
        }
    }

    int Query(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += c[pos];
            pos -= LowBit(pos);
        }
        return ret;
    }

    void Discretization(vector<int> &nums) {
        a.assign(nums.begin(), nums.end());
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }

    int getId(int x) {
        return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
    }

public:
    // 方法一：离散化树状数组
    vector<int> countSmaller(vector<int> &nums) {
        vector<int> resultList;
        Discretization(nums);
        Init(nums.size() + 5);

        for (int i = (int) nums.size() - 1; i >= 0; --i) {
            int id = getId(nums[i]);
            resultList.push_back(Query(id - 1));
            Update(id);
        }

        reverse(resultList.begin(), resultList.end());
        return resultList;
    }
};


int main() {
    Solution solution;
    vector<int> nums = {3, 9, 5, 2, 6, 1, 3};
    vector<int> resultList = solution.countSmaller(nums);
    for (auto num: resultList) {
        printf("%d\t", num);
    }
    return 0;
}
